package com.caoyanan.algorithm.question.zuoTraining.training004.class03;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最短获取咖啡时间
 *
 * 给一个长度为N的数组arr， 代表有N台咖啡机，数组中每个数字代表咖啡机生产1倍咖啡的时间，同一个咖啡机只能串行生产，不同的咖啡机可以并行工作
 * 有M个人，求每个人最早获取咖啡的时间，返回一个数组
 * @author: caoyanan
 * @time: 2021/6/19 19:49
 */
public class Question04_ShortestTimeGetCoffee {

    public static void main(String[] args) {

        int[] arr = {3, 1, 7};
        int m = 15;
        System.out.println(Arrays.toString(everyOneGetCoffeeTime(arr, m)));
    }

    /**
     * 给一个数组，表示咖啡生产1杯咖啡需要的时间，返回m个人的每个人最早获取咖啡的实现，同一个咖啡只能串行工作，但是不同的咖啡可以并行工作
     * 准备一个小顶堆，元素里面放 一杯咖啡的开始时间和结束时间，
     * 比如 {3, 1, 7}, 一开始放入 (0, 3), (0, 1), (0, 7)，即开始时间，和需要工作的时间，以总和作为排列依据
     * 第一个人1时间拿到 变成(1, 1)， 第二个人2时间拿到，放入(2,1) ，第三个人3时间拿到，放入(3,1),第4个人也3时间拿到，放入 (3,3)
     *
     * @param arr
     * @param m
     * @return
     */
    private static int[] everyOneGetCoffeeTime(int[] arr, int m) {

        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());
        for (int i = 0; i < arr.length; i++) {
            queue.add(new Node(0, arr[i]));
        }

        int[] answer = new int[m];
        for (int i = 0; i < m; i++) {
            Node poll = queue.poll();
            answer[i] = poll.beginTime + poll.workTime;
            queue.add(new Node(answer[i], poll.workTime));
        }
        return answer;
    }

    public static class Node {
        public int beginTime;
        public int workTime;

        public Node(int beginTime, int workTime) {
            this.beginTime = beginTime;
            this.workTime = workTime;
        }
    }

    public static class NodeComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.beginTime + o1.workTime - o2.beginTime - o2.workTime;
        }
    }
}
